// 给你一个整数数组 nums，请你将该数组升序排列。

//  

// 示例 1：

// 输入：nums = [5,2,3,1]
// 输出：[1,2,3,5]
// 示例 2：

// 输入：nums = [5,1,1,2,0,0]
// 输出：[0,0,1,1,2,5]
//  

// 提示：

// 1 <= nums.length <= 50000
// -50000 <= nums[i] <= 50000

#include "stdc++.h"

/* 稳定性
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，
这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，
而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的。
*/

/* 01 插入排序 - 超时
遍历数组元素，并且将这个元素与前面的所有元素进行比较，然后插入到合适的位置
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        insertionSort(nums);
        return nums;
    }
private:
    void insertionSort(vector<int>& nums) {
        int n = nums.size();
        for (int i{1}; i < n; ++i) {
            int j{i};
            int cur = nums[i]; // 当前的数字
            for (; j > 0 && nums[j - 1] > cur; --j) {
                nums[j] = nums[j - 1];
            }
            nums[j] = cur;
        }
    }
};

/* 02 希尔排序
这个是插入排序的修改版，根据步长由长到短分组，进行排序，直到步长为1为止，属于插入排序的一种。
时间复杂度：O(n^1.3)
空间复杂度：O(1)
稳定性：不稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        shellSort(nums);
        return nums;
    }
private:
    void shellSort(vector<int>& nums) {
        int n = nums.size();
        for (int gap{n / 2}; gap >= 1; gap /= 2) {
            for (int i{gap}; i < n; ++i) {
                int cur = nums[i];
                int j{i};
                for (; j >= gap && nums[j - gap] > cur; j -= gap) {
                    nums[j] = nums[j - gap];
                }
                nums[j] = cur;
            }
        }
    }
};

/* 03 基数排序
Radix Sort
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，
然后按每个位数分别比较。排序过程是将所有待比较数值统一为同样的数位长度，
数位较短的数前面补零，然后从最低位开始，依次进行一次排序。
这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
时间复杂度：O(d*(r+n)) d代表长度，n代表关键字的个数，r代表关键字的基数
空间复杂度：O(rd+n)
稳定性：稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        radixSort(nums);
        return nums;
    }
private:
    void radixSort(vector<int>& nums) {
        int n = nums.size();
        int m = getMax(nums, n);
        for (int exp{1}; m / exp > 0; exp *= 10) {
            countSort(nums, n, exp);
        }
    }
    int getMax(vector<int>& nums, int n) {
        int mx = nums[0];
        for (int i{1}; i < n; ++i) {
            if (nums[i] > mx) {
                mx = nums[i];
            }
        }
        return mx;
    }
    void countSort(vector<int>& nums, int n, int exp) {
        vector<int> output(n, 0);
        int i{0};
        vector<int> count(10, 0);
        for (; i < n; ++i) {
            count[(nums[i] / exp) % 10]++;
        }
        for (i = 1; i < 10; ++i) {
            count[i] += count[i - 1];
        }
        for (i = n - 1; i >= 0; --i) {
            output[count[(nums[i] / exp) % 10] - 1] = nums[i];
            count[(nums[i] / exp) % 10]--;
        }
        for (i = 0; i < n; i++) {
            nums[i] = output[i];
        }
    }
};

/* 04 冒泡排序 - 超时
时间复杂度：O(n^2)
空间复杂度：O(1)
稳定性：稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        for (int i{n}; i >= 1; --i) {
            for (int j{1}; j < i; ++j) {
                if (nums[j-1] > nums[j]) {
                    swap(nums[j-1], nums[j]);
                }
            }
        }
        return nums;
    }
};

/* 05 归并排序
归并排序相比较之前的排序算法而言加入了分治法的思想，其算法思路如下：
1.如果给的数组只有一个元素的话，直接返回（也就是递归到最底层的一个情况）
2.把整个数组分为尽可能相等的两个部分（分）
3.对于两个被分开的两个部分进行整个归并排序（治）
4.把两个被分开且排好序的数组拼接在一起
时间复杂度：O(NlogN)
空间复杂度：O(n)
稳定性：稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        tmp.resize(n, 0);
        mergeSort(nums, 0, n - 1);
        return nums;
    }
private:
    vector<int> tmp{};
    void mergeSort(vector<int>& nums, int l, int r) {
        if (l >= r) {
            return;
        }
        int mid = l + (r - l) / 2;
        mergeSort(nums, l, mid); // 对 nums 数组里 [l,mid] 部分进行排序
        mergeSort(nums, mid + 1, r); // 对 nums 数组里 [mid+1,r] 部分进行排序
        int i{l};
        int j{mid + 1};
        int count{0};
        while (i <= mid && j <= r) {
            if (nums[i] < nums[j]) {
                tmp[count++] = nums[i++];
            } else {
                tmp[count++] = nums[j++];
            }
        }
        while (i <= mid) {
            tmp[count++] = nums[i++];
        }
        while (j <= r) {
            tmp[count++] = nums[j++];
        }
        for (int i{0}; i < r - l + 1; ++i) {
            nums[i + l] = tmp[i];
        }
    }
};

/* 06 堆排序
堆排序是一种基于二叉堆（Binary Heap）结构的排序算法，所谓二叉堆，
我们通过完全二叉树来对比，只不过相比较完全二叉树而言，
二叉堆的所有父节点的值都大于（或者小于）它的孩子节点。

最大堆的定义：
    最大堆中的最大元素值出现在根结点（堆顶）
    堆中每个父节点的元素值都大于等于其孩子结点

时间复杂度：O(NlogN)
空间复杂度：O(1)
稳定性：稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        heapSort(nums);
        return nums;
    }
private:
    // 堆排序的方法如下，把最大堆堆顶的最大数取出，将剩余的堆继续调整为最大堆，
    // 再次将堆顶的最大数取出，这个过程持续到剩余数只有一个时结束。
    void heapSort(vector<int>& nums) {
        int n = nums.size();
        // 建堆
        for (int i{n / 2 - 1}; i >= 0; --i) {
            heapify(nums, n, i);
        }
        // 从堆顶取出元素
        for (int i{n - 1}; i >= 0; --i) {
            swap(nums[0], nums[i]); // 堆顶元素nums[0]放在i处
            heapify(nums, i, 0);
        }
    }
    // 调整堆，i表示当前要调整的元素下标（当前的堆顶）
    void heapify(vector<int>& nums, int n, int i) {
        int largest = i; // 将最大元素设置为堆顶元素
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        // 左孩子比root大
        if (left < n && nums[left] > nums[largest]) {
            largest = left;
        }
        // 右孩子比root大
        if (right < n && nums[right] > nums[largest]) {
            largest = right;
        }
        if (largest != i) {
            swap(nums[i], nums[largest]);
            heapify(nums, n, largest); // 递归地调整子堆
        }
    }
};

/* 07 桶排序
桶排序的原理是将数组分到有限数量的桶中，
再对每个桶子再分别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序），
最后将各个桶中的数据有序的合并起来。
排序过程：
    假设待排序的一组数统一的分布在一个范围中，并将这一范围划分成几个子范围，也就是桶
    将待排序的一组数，分档规入这些子桶，并将桶中的数据进行排序
    将各个桶中的数据有序的合并起来
时间复杂度：O(n+k)
空间复杂度：O(n*k)
稳定性：
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        bucketSort(nums, n);
        return nums;
    }
private:
    void bucketSort(vector<int>& nums, int n) {
        // 1. 创建n个空桶
        vector<vector<int>> buckets(n, vector<int>());
        // 2. 把数组元素放入不同的桶中
        for (const auto& num : nums) {
            int i = n * num % n; // index in bucket
            buckets[i].push_back(num);
        }
        // 3. 对每个桶排序
        for (auto& bucket : buckets) {
            sort(bucket.begin(), bucket.end());
        }
        // 4. 把各个桶连接成nums
        int index{0};
        for (int i{0}; i < n; ++i) {
            for (int j{0}; j < buckets[i].size(); ++j) {
                nums[index++] = buckets[i][j]; 
            }
        }
    }
};

/* 08 快速排序
时间复杂度：O(NlogN)
空间复杂度：O(NlogN)
稳定性：不稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        quickSort(nums, 0, n - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int left, int right) {
        if (left > right) return;
        int pivot = nums[left]; // 最左边作为主元
        int i{left};
        int j{right};
        while (i < j) {
            // 选左边为主元就要先动右边
            while (i < j && nums[j] >= pivot) --j;
            while (i < j && nums[i] <= pivot) ++i;
            swap(nums[i], nums[j]);
        }
        swap(nums[i], nums[left]);
        quickSort(nums, left, i - 1);
        quickSort(nums, i + 1, right);
    }
};

/* 08 快速排序 - 漂亮简洁
时间复杂度：O(NlogN)
空间复杂度：O(NlogN)
稳定性：不稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();
        qSort(nums, 0, n - 1);
        return nums;
    }
    void qSort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int i{l};
            int j{r};
            int v{nums[l]}; // pivot
            while (i < j) {
                while (i < j && nums[j] >= v) --j;
                while (i < j && nums[i] <= v) ++i;
                swap(nums[i], nums[j]);
            }
            swap(nums[i], nums[l]);
            qSort(nums, l, i - 1);
            qSort(nums, i + 1, r);
        }
    }
};

/* 08 快速排序 - 随机选择主元
时间复杂度：O(NlogN)
空间复杂度：O(NlogN)
稳定性：不稳定
*/
class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        srand(static_cast<unsigned>(time(nullptr)));
        int n = nums.size();
        randomized_quickSort(nums, 0, n - 1);
        return nums;
    }
private:
    int partition(vector<int>& nums, int left, int right) {
        int pivot = nums[right];
        int i{left - 1};
        for (int j{left}; j <= right - 1; ++j) {
            if (nums[j] <= pivot) {
                i += 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[right]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int left, int right) {
        int i = rand() % (right - left + 1) + left; // 随机选择主元
        swap(nums[i], nums[right]);
        return partition(nums, left, right);
    }
    void randomized_quickSort(vector<int>& nums, int left, int right) {
        if (left < right) {
            int pos = randomized_partition(nums, left, right);
            // 每次pos位置的数就定下来了
            randomized_quickSort(nums, left, pos - 1);
            randomized_quickSort(nums, pos + 1, right);
        }
    }
};
